//在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]
//,["1","0","0","1","0"]]
//输出：4
// 
//
// 示例 2： 
//
// 
//输入：matrix = [["0","1"],["1","0"]]
//输出：1
// 
//
// 示例 3： 
//
// 
//输入：matrix = [["0"]]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 300 
// matrix[i][j] 为 '0' 或 '1' 
// 
// Related Topics 数组 动态规划 矩阵 👍 1196 👎 0

package leetcode.editor.cn;

class MaximalSquare {
    public static void main(String[] args) {
        Solution solution = new MaximalSquare().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 暴力法
        /*public int maximalSquare(char[][] matrix) {
            int maxSide = 0;
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return maxSide;
            }
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == '1') {
                        // 将1作为左上角，开始搜索正方形
                        maxSide = Math.max(maxSide, 1);

                        // 计算可能搜索的最大边界，防止越界
                        int maxLength = Math.min(matrix.length - i, matrix[0].length - j);

                        for (int k = 0; k < maxLength; k++) {
                            // 表示现在是否符合正方形
                            // 判断新增的一行一列是否均为 1
                            boolean flag = true;
                            // 对角不为1，不需要搜索了
                            if (matrix[i + k][j + k] == '0') break;

                            for (int l = 0; l < k; l++) {
                                if (matrix[i + l][j + k] == '0' || matrix[i + k][j + l] == '0') {
                                    // 不满足设置标志为false
                                    flag = false;
                                    break;
                                }
                            }

                            if (flag) {
                                // 更新最大边
                                maxSide = Math.max(k + 1, maxSide);
                            } else break;
                        }
                    }
                }
            }

            return maxSide * maxSide;
        }*/

        /*public int maximalSquare(char[][] matrix) {
            int maxSide = 0;
            if (matrix.length == 0 || matrix[0].length == 0 || matrix == null) return maxSide;

            // dp[i]表示：当前以i为矩形的最大边长
            int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
            // 初始化都为0
            for (int i = 1; i <= matrix.length; i++) {
                for (int j = 1; j <= matrix[0].length; j++) {
                    if (matrix[i - 1][j - 1] == '1') {
                        // 三者取最大
                        dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                        maxSide = Math.max(maxSide, dp[i][j]);
                    }
                }
            }

            return maxSide * maxSide;
        }*/

        // y优化
        public int maximalSquare(char[][] matrix) {
            int maxSide = 0;
            if (matrix.length == 0 || matrix[0].length == 0 || matrix == null) return maxSide;

            // dp[i]表示：当前以i为矩形的最大边长
            int[] dp = new int[matrix[0].length + 1];
            // 初始化都为0
            for (int i = 1; i <= matrix.length; i++) {
                int northwest = 0;
                for (int j = 1; j <= matrix[0].length; j++) {
                    int nextNorthwest = dp[j];
                    if (matrix[i - 1][j - 1] == '1') {
                        // 三者取最大
                        dp[j] = Math.min(dp[j], Math.min(dp[j - 1], northwest)) + 1;
                        maxSide = Math.max(maxSide, dp[j]);
                    }else dp[j] = 0;
                    northwest = nextNorthwest;
                }
            }

            return maxSide * maxSide;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
